Linear Search হল একটি সহজ এবং মৌলিক সার্চিং পদ্ধতি যা একটি তালিকার প্রতিটি উপাদানকে একে একে পরীক্ষা করে। যখন একটি লক্ষ্য উপাদান পাওয়া যায়, তখন তার ইনডেক্স ফেরত দেয়। যদি উপাদানটি তালিকায় না পাওয়া যায়, তবে এটি সাধারণত -1 ফেরত দেয়।
Linear Search এর কাজের পদ্ধতি:
- প্রথমে তালিকার প্রথম উপাদান পরীক্ষা করা হয়।
- যদি প্রথম উপাদানটি লক্ষ্য উপাদানের সমান হয়, তাহলে সেই ইনডেক্স ফেরত দেওয়া হয়।
- যদি নয়, তবে পরবর্তী উপাদানে যাওয়া হয় এবং পুনরাবৃত্তি করা হয়।
- এটি শেষ উপাদান পর্যন্ত চলতে থাকে যতক্ষণ না লক্ষ্য উপাদান পাওয়া যায় অথবা তালিকার শেষ না হয়।
Linear Search এর গঠন
#include <stdio.h>
// Function to perform linear search
int linearSearch(int arr[], int size, int target) {
for (int i = 0; i < size; i++) {
if (arr[i] == target) {
return i; // Return index if target is found
}
}
return -1; // Return -1 if target is not found
}
int main() {
int arr[] = {10, 20, 30, 40, 50}; // Example array
int size = sizeof(arr) / sizeof(arr[0]);
int target = 30; // Element to search for
int result = linearSearch(arr, size, target);
if (result != -1) {
printf("Element found at index %d\n", result);
} else {
printf("Element not found\n");
}
return 0;
}
১. কোড বিশ্লেষণ
linearSearch ফাংশন:
- ইনপুট হিসেবে একটি অ্যারে, এর সাইজ এবং লক্ষ্য উপাদান গ্রহণ করে।
- একটি লুপের মাধ্যমে প্রতিটি উপাদান পরীক্ষা করে।
- যদি লক্ষ্য উপাদান পাওয়া যায়, তবে ইনডেক্স ফেরত দেয়।
- না হলে, -1 ফেরত দেয়।
main ফাংশন:
- একটি উদাহরণ অ্যারে তৈরি করে এবং একটি লক্ষ্য উপাদান নির্ধারণ করে।
linearSearchফাংশন কল করে এবং ফলাফল প্রিন্ট করে।
২. Linear Search এর সময় জটিলতা
- Worst Case: O(n) - যদি লক্ষ্য উপাদান তালিকার শেষ উপাদান হয় বা তালিকায় না থাকে।
- Best Case: O(1) - যদি লক্ষ্য উপাদান তালিকার প্রথম উপাদান হয়।
- Average Case: O(n) - গড় ক্ষেত্রে, এটি প্রায় অর্ধেক উপাদান পরীক্ষা করতে হয়।
Content added By
Read more
